package binaryTree;

import java.util.LinkedList;

public class MaxDepth {
    //层序遍历实现
    public int maxDepth(TreeNode root) {
        int maxDepth=0;
        LinkedList<TreeNode>  list = new LinkedList<>();
        if (root!=null){
            list.add(root);
        }
        while (!list.isEmpty()) {
            maxDepth++;
            int size = list.size();
            while (size > 0) {
                TreeNode cur = list.poll();
                if (cur.left!=null){
                    list.add(cur.left);
                }
                if (cur.right!=null){
                    list.add(cur.right);
                }
                size--;
            }

        }
        return  maxDepth;
    }

    public  int maxDepth1(TreeNode root){
        //后序遍历  左右根来记录深度
        if (root==null){
            return  0;
        }
        int i = maxDepth1(root.left);    //左边遍历
        int i1 = maxDepth1(root.right);   //右边遍历
        return 1+Math.max(i,i1);    //根节点  处理
    }


//    本题可以使用前序，也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序呢求的是高度。
//
//    而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度，所以二叉树：
//    看看这些树的最大深度 (opens new window)中使用的是后序遍历。


}
